package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 二叉树的前序遍历144
 *给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * @author: chaidl  ！
 * @create: 2022-04-11 15:09
 */
public class 二叉树的前序遍历144 {
	//采用迭代的方式
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		Deque<TreeNode> stack=new LinkedList<>();
		while (root !=null || !stack.isEmpty()){
			while (root != null){
				result.add(root.val);
				stack.push(root);
				root=root.left;
			}
			root=stack.pop();
			root=root.right;
		}
		return result;
	}
	//采用递归的方式
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		accessTree(root,result);
		return result;
	}
	//采用递归的方式
	private void accessTree(TreeNode root, List<Integer> result) {
		if (root == null){
			return;
		}
		result.add(root.val);
		accessTree(root.left,result);
		accessTree(root.right,result);
	}
}
